<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            function BinarySearchTree() {
                function Node(key) {
                    this.key = key;
                    this.left = null;
                    this.right = null;
                }
                this.root = null;
                BinarySearchTree.prototype.insert = function (key) {
                    var newNode = new Node(key);
                    if (this.root == null) {
                        this.root = newNode;
                    } else {
                        this.insertNode(this.root, newNode);
                    }
                };
                BinarySearchTree.prototype.insertNode = function (node, newNode) {
                    if (node.key > newNode.key) {
                        if (node.left == null) {
                            node.left = newNode;
                        } else {
                            this.insertNode(node.left, newNode);
                        }
                    } else {
                        if (node.right == null) {
                            node.right = newNode;
                        } else {
                            this.insertNode(node.right, newNode);
                        }
                    }
                };
                // 先序遍历
                BinarySearchTree.prototype.preOrderTravelsal = function (handler) {
                    this.preOrderTravelsalNode(this.root, handler);
                };
                BinarySearchTree.prototype.preOrderTravelsalNode = function (node, handler) {
                    if (node != null) {
                        handler(node.key);
                        this.preOrderTravelsalNode(node.left, handler);
                        this.preOrderTravelsalNode(node.right, handler);
                    }
                };
                // 中序遍历
                BinarySearchTree.prototype.midOrderTravelsal = function (handler) {
                    this.midOrderTravelsalNode(this.root, handler);
                };
                BinarySearchTree.prototype.midOrderTravelsalNode = function (node, handler) {
                    if (node != null) {
                        this.midOrderTravelsalNode(node.left, handler);
                        handler(node.key);
                        this.midOrderTravelsalNode(node.right, handler);
                    }
                };
                // 后序遍历
                BinarySearchTree.prototype.postOrderTravelsal = function (handler) {
                    this.postOrderTravelsalNode(this.root, handler);
                };
                BinarySearchTree.prototype.postOrderTravelsalNode = function (node, handler) {
                    if (node != null) {
                        this.postOrderTravelsalNode(node.left, handler);
                        this.postOrderTravelsalNode(node.right, handler);
                        handler(node.key);
                    }
                };
                // 最大值
                BinarySearchTree.prototype.max = function () {
                    var node = this.root;
                    while (node != null) {
                        var key = node.key;
                        node = node.right;
                    }
                    return key;
                };
                // 最小值
                BinarySearchTree.prototype.min = function () {
                    var node = this.root;
                    while (node != null) {
                        var key = node.key;
                        node = node.left;
                    }
                    return key;
                };
                // 搜索
                BinarySearchTree.prototype.search = function (key) {
                    var node = this.root;
                    return this.searchNode(this.root, key);
                };

                BinarySearchTree.prototype.searchNode = function (node, key) {
                    if (node == null) {
                        return false;
                    }
                    if (node.key > key) {
                        return this.searchNode(node.left, key);
                    } else if (node.key < key) {
                        return this.searchNode(node.right, key);
                    } else {
                        return true;
                    }
                };
                // 删除
                BinarySearchTree.prototype.remove = function (key) {
                  
                };
            }
            var binarySearchTree = new BinarySearchTree();
            binarySearchTree.insert(11);
            binarySearchTree.insert(7);
            binarySearchTree.insert(15);
            binarySearchTree.insert(5);
            binarySearchTree.insert(3);
            binarySearchTree.insert(9);
            binarySearchTree.insert(8);
            binarySearchTree.insert(10);
            binarySearchTree.insert(13);
            binarySearchTree.insert(12);
            binarySearchTree.insert(14);
            binarySearchTree.insert(20);
            binarySearchTree.insert(18);
            binarySearchTree.insert(25);
            var str = '';
            binarySearchTree.preOrderTravelsal(key => (str += key + ' '));
            console.log('先序遍历：' + str);
            var str = '';
            binarySearchTree.midOrderTravelsal(key => (str += key + ' '));
            console.log('中序遍历：' + str);
            var str = '';
            binarySearchTree.postOrderTravelsal(key => (str += key + ' '));
            console.log('后序遍历：' + str);
            //    console.log(binarySearchTree.max());

            console.log(binarySearchTree.search(25));
        </script>
    </body>
</html>
